
// https://leetcode.cn/problems/letter-case-permutation/

class Solution
{
    vector<string> res;
    string path;
    int n;

public:
    vector<string> letterCasePermutation(string s)
    {
        n = s.size();
        dfs(s, 0);
        return res;
    }

    void dfs(string& s, int idx)
    {
        if (path.size() == n)
        {
            res.push_back(path);
            return;
        }

        if (check(s[idx]))
        {
            if (s[idx] >= 'a' && s[idx] <= 'z')
            {
                path += s[idx];
                dfs(s, idx + 1);
                path.pop_back();
                path += s[idx] - 32;
                dfs(s, idx + 1);
                path.pop_back();
            }
            else
            {
                path += s[idx];
                dfs(s, idx + 1);
                path.pop_back();
                path += s[idx] + 32;
                dfs(s, idx + 1);
                path.pop_back();
            }
        }
        else
        {
            path += s[idx];
            dfs(s, idx + 1);
            path.pop_back();
        }
    }

    bool check(char c)
    {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }
};